package formal.string;

import java.util.HashMap;

/**
 * @author DengYuan2
 * @create 2021-02-01 20:59
 */
public class E_409 {

    public static void main(String[] args) {
        String s = "abdcdbcc";
        int res = longestPalindrome2(s);
        System.out.println(res);
    }

    /**
     * 我的思路：偶数个就直接相加，有奇数的话加上其偶数部分，最后再看看有没有奇数，有的话加1
     * 可以，但是很慢很慢
     *
     * @param s
     * @return
     */
    public static int longestPalindrome(String s) {
        int longest = 1;
        int evenSum = 0;
        int oddCount = 0;
        HashMap<Character, Integer> map = new HashMap<>();
        for (char ch : s.toCharArray()) {
            map.put(ch, map.getOrDefault(ch, 0) + 1);
        }
        for (char ch : map.keySet()) {
            Integer count = map.get(ch);
            evenSum += count;
            if (count % 2 != 0) {
                oddCount += 1;
                evenSum -= 1;
            }
        }
        longest = evenSum + Math.min(1, oddCount);
        return longest;
    }

    /**
     * 大神-还是利用了数组及其索引，不过这次char直接就是索引
     *
     * @param s
     * @return
     */
    public static int longestPalindrome2(String s) {
        int longest = 0;
        int[] counts = new int[256];
        for (char ch : s.toCharArray()) {
            counts[ch]++;
        }
        for (int cnt:counts){
            //这种写法真是太机智了，直接加上其偶数部分
            longest+=cnt/2*2;
        }
        // 若满足该if条件，则存在奇数，故要加1
        if (longest<s.length()){
            longest++;
        }
        return longest;

    }
}
